def mergesort(list_my):  # 递归直到子数组元素个数少于1
    if len(list_my) <= 1:
        return list_my

    mid = len(list_my) // 2
    l_list = mergesort(list_my[:mid])
    r_list = mergesort(list_my[mid:])
    return merge(l_list, r_list)


def merge(l_list, r_list):  # 依据子数组元素大小合并子数组
    result = []
    i = j = 0
    while i < len(l_list) and j < len(r_list):
        if l_list[i] < r_list[j]:
            result.append(l_list[i])
            i += 1
        else:
            result.append(r_list[j])
            j += 1
    if i == len(l_list):
        while j < len(r_list):
            result.append(r_list[j])
            j += 1
    else:
        while i < len(l_list):
            result.append(l_list[i])
            i += 1
    return result


def main():
    rand_array = [5, 3, 9, 7, 8, 2, 4]
    print(rand_array)
    result = mergesort(rand_array)
    print(result)


if __name__ == '__main__':
    main()
